# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/25 22:22
@FileName      : 迪杰斯特拉算法.py
@LastEditors   : None
@Editors       : PyCharm
"""
N = 7
cost_dict = {"0-1": 2, "1-3": 5, "0-2": 6, "2-3": 8, "3-5": 15, "3-4": 10, "4-5": 6, "5-6": 6, "4-6": 2}
cost = [[0] * N for n in range(N)]
for key in cost_dict:
    p1, p2 = [int(p) for p in key.split('-')]
    value = cost_dict[key]
    cost[p1][p2] = value
    cost[p2][p1] = value


class Point():
    def __init__(self, n):
        self.p = n
        self.weight = float('inf')
        self.paths = []
        self.referer = None
        self.k = False


def print_points(points):
    str1 = '\n'.join(
        ["0-%d的最短路径中的顶点有：" % point.p + '-'.join([str(p) for p in point.paths]) for point in points])
    str2 = '\n'.join("0-%d：%d" % (point.p, point.weight) for point in points)
    print("最短路径为：")
    print(str1)
    print("源点到各顶点的最短路径长度为:")
    print(str2)


def Dijkstra_minTree(cost, N):
    points = [Point(i) for i in range(N)]
    # 初始化
    points[0].k = True
    points[0].weight = 0
    points[0].paths = [0]

    start = 0
    for i in range(N - 1):
        pre_weight = points[start].weight
        for p in range(N):
            if start == points[p].referer:
                continue
            weight = cost[start][p]
            if weight != 0:
                weight += pre_weight
                if points[p].weight > weight:
                    points[p].weight = weight
                    points[p].referer = start
                    points[p].paths = points[start].paths + [p]
        weight = float('inf')
        for i in range(1, N):
            if points[i].weight < weight and not points[i].k:
                weight = points[i].weight
                start = i
        points[start].k = True
    return points[1:]


points = Dijkstra_minTree(cost, N)
print_points(points)
